from tools_algorithm import *


class Solution:
    def minimumTimeToInitialState(self, word: str, k: int) -> int:
        n = len(word)
        z = [0] * n
        l = r = 0
        for i in range(1, n):
            z[i] = 0 if i > r else min(z[i - l], r - i + 1)
            while (j := i + z[i]) < n and word[z[i]] == word[j]:
                l, r = i, j
                z[i] += 1
        for i in range(k, n, k):
            if z[i] == n - i:
                return i // k
        return (n + k - 1) // k


s = Solution()
print(s.minimumTimeToInitialState(word="abacaba", k=3))
